public class RedBlue {
    /**
     * 关于红蓝染色法
     * <p>
     * 这是对二分法的升级，解决二分法的边界问题
     *
     * @param args
     */
    public static void main(String[] args) {
        // 满足条件，染成蓝色
        // 不满足条件，染成红色

        int[] nums = {5, 7, 7, 8, 8, 10};
        int target = 8;

        int result = findFirstGreaterOrEqual(nums, target);
        System.out.println("第一个大于等于 " + target + " 的位置是: " + result);

    }

    public static int findFirstGreaterOrEqual(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        // 红蓝染色法，蓝色是满足条件，红色是不满足条件
        while (left < right) {
            int mid = left + (right - left) / 2; // 避免溢出
            if (nums[mid] >= target) {
                // 中间满足条件，说明右边的全部满足条件，缩小右边界，把右边全部染成蓝色
                right = mid;
            } else {
                // 不满足条件，染成红色，缩小左边界
                left = mid + 1;
            }
        }

        // 检查最后的 left 是否满足条件
        // 如果目标值比数组中所有元素都大，left 会指向数组末尾
        if (nums[left] >= target) {
            return left;
        } else {
            return left + 1; // 目标值需要插入到数组末尾
        }
    }

}
